package LeetCode;

import java.util.*;

public class LC_621_TaskScheduler {

    public static void main(String[] args) {

    }

    public class Solution_1 {
        public int leastInterval(char[] tasks, int n) {
            if (tasks == null) return 0;
            int len = tasks.length;
            Map<Character, Integer> map = new HashMap<>();
            int maxFrequency = 0;
            for (char c : tasks) {
                map.put(c, map.getOrDefault(c, 0) + 1);
                maxFrequency = Math.max(maxFrequency, map.get(c));
            }
            int count = 0;
            for (int frequency : map.values()) {
                if (frequency == maxFrequency) {
                    count++;
                }
            }
            return Math.max(len, (maxFrequency - 1) * (n + 1) + count);
        }
    }


    public class Solution_2 {
        public int leastInterval(char[] tasks, int n) {
            Map<Character, Integer> map = new HashMap<>();
            for (char c : tasks) {
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
            PriorityQueue<Integer> queue = new PriorityQueue<>((e1, e2) -> e2 - e1);
            queue.addAll(map.values());
            int count = 0;
            while (!queue.isEmpty()) {
                int k = n + 1;
                List<Integer> next = new ArrayList<>();
                while (!queue.isEmpty() && k > 0) {
                    int target = queue.poll();
                    if (target - 1 > 0) {
                        next.add(target - 1);
                    }
                    count++;
                    k--;
                }
                if (!next.isEmpty()) {
                    count += k;
                }
                queue.addAll(next);
            }
            return count;
        }
    }


    public class Solution_3 {
        public int leastInterval(char[] tasks, int n) {
            int[] val = new int[26];
            for (char task : tasks) {
                val[task - 'A']++;
            }
            Arrays.sort(val);
            int i = 25;
            while (i >= 0 && val[i] == val[25]) i--;
            return Math.max(tasks.length, (val[25] - 1) * (n + 1) + 25 - i);
        }
    }

}